"""
A general implementation of simulated annealing (sa).

Simulated annealing has its roots in metallurgy, where materials are heated
and then cooled to alter their physical properties. Simulated annealing
similarly keeps track of the system's "temperature", and accepts solutions
with greater randomness when the temperature is high. This helps the
algorithm resist becoming stuck in local optima early on. As the system
cools, its propensity for randomness decreases, and it essentially becomes a
basic hill climber.

Most functions in this module are higher-order functions that return another
function. To create an SA optimizer, you must minimally call create_optimizer
with a measure_energy (aka fitness) function, a change_state (aka mutate)
function, and values for the initial temperature and temperature reduction.

Copyright (C) 2013 Jerrad Michael Genson

This program is free software: you can redistribute it and/or modify
it under the terms of the BSD 3-Clause License as published by
the Open Source Initiative.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
BSD 3-Clause License for more details.

You should have received a copy of the BSD 3-Clause License
along with this program.  If not, see
<https://betelgeuse-ml.googlecode.com/hg/LICENSE>

"""

# Python built-in modules
import math
import random

# Module header
__author__ = 'Jerrad Genson'
__contact__ = 'jerradgenson@gmail.com'
__copyright__ = 'Copyright 2013 Jerrad Michael Genson'
__license__ = 'BSD 3-Clause'


def create_optimizer(measure_energy, change_state,
                     temperature, reduction, magnitude=0.1):
    """
    Create an optimizer using simulated annealing.

    Args:
        measure_energy: A function that takes a system state as input and
                        returns its energy level as a value between 0 and
                        1, where lower energies are better.
        change_state: A function that randomly changes the state of a given
                      system. It takes a system state as input, along with
                      the magnitude of the change, and returns a new state.
        temperature: The temperature to start the annealing schedule at.
        reduction: A real value between 0 and 1 to reduce temperature by
                   after each cycle of annealing.

    Keywords:
        magnitude: Magnitude of each state change as a real value between
                   0 and 1.

    Returns:
        An optimizer function that uses simulated annealing. This function is
        not reusable, since it must preserve the state of the annealing
        schedule.

    """

    def sa_optimize(system_states):
        """
        Simulated annealing optimizer.

        Args:
            system_states: A list of system states, represented by Numpy Arrays.

        Returns:
            A new list of system states, after applying one cycle of simulated annealing.

        """

        nonlocal temperature

        new_states = []
        # Apply annealing to every system state.
        for state in system_states:
            # Randomly change value of state.
            new_state = change_state(state, magnitude)
            # Compute energy of new and old states.
            old_energy = measure_energy(state)
            new_energy = measure_energy(new_state)
            if new_energy < old_energy:
                # New state has less energy, so keep it.
                new_states.append(new_state)

            elif math.exp((old_energy - new_energy) / temperature) > random.random():
                # Allow more expensive energy state to escape local minima, as
                # per the Boltzmann distribution.
                new_states.append(new_state)

            else:
                # Keep the old state.
                new_states.append(state)

        # Apply annealing schedule to reduce temperature.
        temperature = temperature * reduction

        return new_states

    return sa_optimize
